/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 *                                                                           *
 *                          Copyright (c) 2010                               *
 *                  Alen Stojanov [ ioi.alen@gmail.com ]                     *
 *                Jacobs University Bremen, Bremen, Germany                  *
 *                                                                           *
 *                          All Rights Reserved.                             *
 *                                                                           *
 *    Permission to use, copy, modify and distribute this software and       *
 *    its documentation is hereby granted, provided that both the            *
 *    copyright notice and this permission notice appear in all copies of    *
 *    the software, derivative works or modified versions, and any           *
 *    portions thereof, and that both notices appear in supporting           *
 *    documentation.                                                         *
 *                                                                           *
 *    This code is distributed in the hope that it will be useful, but       *
 *    WITHOUT ANY WARRANTY; without even the implied warranty of             *
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS       *
 *    DISCLAIM ANY LIABILITY OF ANY KIND FOR ANY DAMAGES WHATSOEVER          *
 *    RESULTING FROM THE USE OF THIS SOFTWARE.                               *
 *                                                                           *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

/*
 **************************************************************************
 * Class: Graham Scan Convex Hull                                         *
 * By Arash Partow - 2001                                                 *
 * URL: http://www.partow.net                                             *
 *                                                                        *
 * Modified code organization by Alen Stojanov [ioi.alen@gmail.com]       *
 * Adapted to comply with Qt's vectors and queues.                        *
 *                                                                        *
 * Copyright Notice:                                                      *
 * Free use of this library is permitted under the guidelines and         *
 * in accordance with the most current version of the Common Public       *
 * License.                                                               *
 * http://www.opensource.org/licenses/cpl.php                             *
 *                                                                        *
 **************************************************************************
 */

#ifndef GRAHAMSCAN_H_
#define GRAHAMSCAN_H_

#include <QVector>
#include <QQueue>

#include <algorithm>
#include <cmath>
#include <vector>

#include "tspoint.h"

// const double _180DivPI  		 = 57.295779513082320876798154814105000;
// const int    counter_clock_wise = +1;
// const int    clock_wise         = -1;

struct GSTSPoint
{
	GSTSPoint(double _x = 0.0, double _y = 0.0,
			double _angle = 0.0) : x(_x), y(_y), angle(_angle) { }
	double x;
	double y;
	double angle;
};

class GSTSPointCompare
{
public:

	GSTSPointCompare(GSTSPoint* _anchor): anchor(_anchor) {};
	bool operator()(const GSTSPoint& p1, const GSTSPoint& p2);

private:
	GSTSPoint* anchor;

	bool is_equal(const GSTSPoint p1, GSTSPoint p2);

	bool is_equal(const double v1, const double& v2,
			const double epsilon = 1.0e-12);

	double lay_distance(const double& x1, const double& y1
			, const double& x2, const double& y2);
};

class GrahamScan
{
public:
	/**
	 * @brief Default constructor
	 */
	GrahamScan(){};
	/**
	 * @brief Default Destructor
	 */
	~GrahamScan(){};

	virtual bool operator()(const QVector < TSPoint >& pnt, QVector< TSPoint >& final_hull);

	const static double _180DivPI  		 = 57.295779513082320876798154814105000;
	const static int    counter_clock_wise = +1;
	const static int    clock_wise         = -1;

private:

	std::vector<GSTSPoint> point;
	GSTSPoint anchor;

	void graham_scan(QVector<TSPoint>& final_hull);

	inline double cartesian_angle(double x, double y);

	inline int orientation(const GSTSPoint& p1,
			const GSTSPoint& p2,
			const GSTSPoint& p3);

	inline int orientation(const double x1, const double y1,
			const double x2, const double y2,
			const double px, const double py);

	inline bool is_equal(const double v1, const double& v2,
			const double epsilon = 1.0e-12);
};


#endif /* GRAHAMSCAN_H_ */
